import java.util.Stack;

public class sevenSort {
    //直接插入排序
    /**
     * 直接插入排序
     * 时间复杂度O(N^2)
     * 稳定
     * @param arr
     */
    public static void insertSort(int [] arr,int start,int end){
        for (int i = start; i <end ; i++) {
          int tmp=arr[i];//记录关键码
            int j=i-1;
            for (; j >=start ; j--) {//插入到0到i-1中
               if(arr[j]>tmp){//tmp小于arr[j]
                   arr[j+1]=arr[j];//将arr[j]向后移一个
                }else{
                   break;
               }
            }
            arr[j+1]=tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度O(2^1.3)
     * 不稳定
     * @param arr
     */
    public  static void shell(int [] arr){
        int gap= arr.length;
        while(gap>1){
            gap=gap/2;
            for (int i = gap; i <arr.length ; i++) {
                int tmp=arr[i];
                int j=i-gap;
                for (; j >=0 ; j=j-gap) {
                    if (arr[j] > tmp) {
                        arr[j + gap] = arr[j];
                    }else{
                        break;
                    }
                }
                arr[j + gap] = tmp;
            }
        }
    }

    /**
     * 选择排序
     * 时间复杂度O（N^2）
     * 不稳定
     * @param arr
     */
    public static  void select(int [] arr){
        //选出最大值和最小值
        int left=0;
        int right=arr.length-1;
        while(left<right) {
            int min=left;
            int max=left;
            for (int i = left+1; i <=right; i++) {
                if (arr[i] < arr[min]) {
                    min =i;
                }
                if (arr[i] >arr[max]) {
                    max = i;
                }
            }
            //最小值和left交换。
            swap(arr,min,left);
            //最大值和right交换
            if(left==max){//这里是害怕max就是left
                max=min;
            }
            swap(arr,max,right);
            left++;
            right--;
        }
    }
    protected static void swap(int [] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

    /**
     * 冒泡排序
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     * 稳定
     * @param arr
     */
    public  static  void bubble(int [] arr){
        for (int i = 0; i < arr.length ; i++) {
            for (int j = 0; j < arr.length-1-i ; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    /**
     * 快速排序
     * 左右指针找基准
     * 时间复杂度O(N*logN)
     * 空间复杂度O(logN)
     * 不稳定
     * @param arr
     */
    public static void quick(int [] arr){
        quickChild(arr,0,arr.length-1);
    }
    protected static void quickChild(int [] arrt ,int star,int end){
       if(star>=end){
           return;
       }
       //小区间的是，待排序的数组是几乎接近有序的。
        //这时候我们可以在小区间直接用插入排序
        /*
        if(end-star>=2){
            insertSort(arrt,star,end);
        }
       //三数取中
        int index=findMidValOfIndex(arrt,star,end);
        swap(arrt,star,index);

         */
        int pivot=partition2(arrt,star,end);
       quickChild(arrt,0,pivot-1);//这是基准前部分
       quickChild(arrt,pivot+1,end);//基准后部分
    }
    //三数取中
    private  static  int findMidValOfIndex(int [] arr,int start,int end){
        int mid=(end+start)/2;
        //大体分两种情况
        if(arr[start]>arr[end]){
            if(arr[mid]>arr[start]){
                return  start;
            }else if(arr[end]>arr[mid]){
                return  end;
            }else{
                return  mid;
            }
        }else{
            if(arr[mid]>arr[start]){
                return  mid;
            }else if(arr[mid]>arr[end]){
                return  end;
            }else{
                return  start;
            }
        }
    }

    //前后指针
    protected static int  partition(int [] arr,int start,int end){
        int pivot=end;
        int prev=start-1;
        int cur=start;
        for (; cur <end ; cur++) {
            if(arr[cur]<=arr[pivot]){
                prev++;
                swap(arr,cur,prev);
            }//这时候cur走到了
        }
        swap(arr,prev+1,pivot);
        return (prev+1);
    }
    //挖坑法
    protected static  int partition2(int [] arr,int start,int end){
        int left=start;
        int tmp=arr[left];
        int right=end;
        while(left<right){
            while(left<right&&arr[right]>=tmp){
                right--;
            }//这时候 right比基准小
            arr[left]=arr[right];
            while(left<right&&arr[left]<=tmp){
                left++;
            }//这是left比基准大
            arr[right]=arr[left];
        }//left和right相遇
        arr[left]=tmp;
        return  left;
    }

    //左右指针
    protected static int partition1(int [] arr,int start ,int end){
        int pivot=start;
        int left=start;
        int right=end;
        while(left<right){
            if(arr[right]>arr[pivot]){
                right--;
            }
            if(arr[left]<arr[pivot]){
                left++;
            }
            //这时候right找到比基准小的数
            //left找到比基准大的数。两者进行交换
            swap(arr,left,right);
        }//left和right相遇
        //left和para交换
        swap(arr,left,pivot);
        //返回基准值
        return  pivot;
    }
    //快排的非递归
    public static  void noquick(int [] arr){
    Stack<Integer>s1=new Stack<>();
    int start=0;
    int end=arr.length-1;
    int index=partition2(arr,start,end);
    //判断左边的数字个数是否大于1；
        if(index-start>1){
            s1.push(start);//左边的头
            s1.push(index-1);//左边的尾
        }
        //判断右边的字数个数是否大于1
        if(end-index>1){
            s1.push(index+1);
            s1.push(end);
        }
        while(!s1.empty()){
            end=s1.pop();//栈是先进后出
            start=s1.pop();
            index=partition2(arr,start,end);
            //判断左边的数字个数是否大于1；
            if(index-start>1){
                s1.push(start);//左边的头
                s1.push(index-1);//左边的尾
            }
            //判断右边的字数个数是否大于1
            if(end-index>1){
                s1.push(index+1);
                s1.push(end);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * wend
     * @param arr
     */
    public static  void merge(int [] arr){
        mergeChild(arr,0,arr.length-1);
    }
    public  static  void mergeChild(int [] arr,int start,int end){
        if(start==end){
            return;
        }//拆分数组
        int mid=(start+end)/2;
        mergeChild(arr,start, mid);
        mergeChild(arr,mid+1,end);
        //合并数组
        merge1(arr,start,mid,end);
    }

    protected static void merge1(int[] arr, int start, int mid, int end) {
        int s1 = start;
        int a1 = mid;
        int s2 = mid + 1;
        int a2 = end;
        int[] tmp = new int[end - start + 1];
        int count = 0;
        while (s1 <= a1 && s2 <= a2) {
            if (arr[s1] <= arr[s2]) {
                tmp[count++] = arr[s1++];
            } else {
                tmp[count++] = arr[s2++];
            }
        }
        while (s1 <= a1) {
            tmp[count++] = arr[s1++];
        }
        while (s2 <= a2) {
            tmp[count++] = arr[s2++];
        }//将数值拷贝到arr数组里面
        for (int i = 0; i < count; i++) {
            arr[i + start] = tmp[i];
        }
    }

}
